#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll dis[301000];
int n,m,s;
struct ed{
int v;ll w;
bool operator < (const ed &x) const{
return x.w<w;
}
};
vector<ed>G[300100];
priority_queue<ed>Q;
vector<int>g[301000];
bool vis[300100];
int ru[301000],sta[301000],sz[301000],top,tmd[301000];
int main(){
scanf("%d%d%d",&n,&m,&s);
for(int u,v,i=1;i<=m;i++){
ll w;scanf("%d%d%lld",&u,&v,&w);
G[u].push_back((ed){v,w});
G[v].push_back((ed){u,w});
}
memset(dis,0x7f,sizeof(dis));
dis[s]=0;Q.push((ed){s,0});
while(!Q.empty()){
ed uu=Q.top();Q.pop();
int u=uu.v;if(vis[u])continue;vis[u]=1;
for(ed t:G[u])if(dis[t.v]>dis[u]+t.w){
dis[t.v]=dis[u]+t.w;
Q.push((ed){t.v,dis[t.v]});
}
}
for(int i=1;i<=n;i++)for(ed t:G[i])if(dis[i]+t.w==dis[t.v])g[i].push_back(t.v),ru[t.v]++;
for(int i=1;i<=n;i++)tmd[i]=i;
sta[++top]=s;
int ans=0;
while(top){
int u=sta[top--],id;
if(tmd[u]!=-1&&tmd[u]!=s)id=tmd[u];
else id=u;
if(id!=s)sz[id]++,ans=max(ans,sz[id]);
for(int v:g[u]){
if(tmd[v]==v)tmd[v]=id;
else if(tmd[v]!=id)tmd[v]=-1;
if(!(--ru[v]))sta[++top]=v;
}
}
return printf("%d",ans),0;
}/*1694389898.3737822*/
566. Reshape the Matrix | 167. Two Sum II - Input array is sorted |
387. First Unique Character in a String | 383. Ransom Note |
242. Valid Anagram | 141. Linked List Cycle |
21. Merge Two Sorted Lists | 203. Remove Linked List Elements |
733. Flood Fill | 206. Reverse Linked List |
83. Remove Duplicates from Sorted List | 116. Populating Next Right Pointers in Each Node |
145. Binary Tree Postorder Traversal | 94. Binary Tree Inorder Traversal |
101. Symmetric Tree | 77. Combinations |
46. Permutations | 226. Invert Binary Tree |
112. Path Sum | 1556A - A Variety of Operations |
136. Single Number | 169. Majority Element |
119. Pascal's Triangle II | 409. Longest Palindrome |
1574A - Regular Bracket Sequences | 1574B - Combinatorics Homework |
1567A - Domino Disaster | 1593A - Elections |
1607A - Linear Keyboard | EQUALCOIN Equal Coins |